//
//  64_最小路径和.swift
//  Swift-LeetCode
//
//  Created by 卢悦明 on 2024/3/7.
/*
 https://leetcode.cn/problems/minimum-path-sum/description/
 */
/**
 1 3 1
 1 5 1
 4 2 1
 */

import UIKit

class GetMinPathSum: NSObject {
    func QA() {
        print(minPathSum([[1,3,1],[1,5,1],[4,2,1]]))
        print("*********8")
        print(minPathSum1([[1,3,1],[1,5,1],[4,2,1]]))

    }
    func minPathSum(_ grid: [[Int]]) -> Int {
        guard let first = grid.first else {
            return 0
        }
        let array = Array(repeating: 0, count: first.count)
        var dp = Array(repeating: array, count: grid.count)
        dp[0][0] = grid[0][0]
        // 第一行
        for i in 1..<first.count {
            dp[0][i] = dp[0][i - 1] + grid[0][i]
        }
        print(dp[0])

        // 第一列
        for i in 1..<dp.count {
            dp[i][0] = dp[i-1][0] + grid[i][0]
        }
        
        for i in 1..<dp.count {
            for j in 1..<first.count {
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
            }
            print(dp[i])

        }
        
        return dp[dp.count - 1][first.count - 1]
    }
    
    /// 一维数组对空间复杂度优化
    func minPathSum1(_ grid: [[Int]]) -> Int {
        guard let first = grid.first else {
            return 0
        }
        let colum = first.count
        var dp = Array(repeating: 0, count: colum)
        dp[0] = first[0]
        for i in 1..<colum {
            dp[i] = dp[i - 1] + first[i]
        }
        for i in 1..<grid.count {
            for j in (0..<first.count) {
                if j == 0 {
                    dp[j] = dp[j] + grid[i][j]
                } else {
                    dp[j] = min(dp[j - 1], dp[j]) + grid[i][j]
                }
            }
        }
        return dp[colum - 1]
    }
    
}
